package com.sort;

import java.util.Arrays;

/**
 * @author yijy
 * @description
 * @create 2021/3/9 上午11:06
 **/
public class MergeSort {

    public static void main(String[] args) {
        int[] arr ={10,1,6,12,8,0,20};
        new MergeSort().sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    private void sort(int[] arr){
        int[] temp = new int[arr.length];
        sort1(arr, 0, arr.length-1, temp);
    }

//    private void sort(int[] arr, int left, int right, int[] temp){
//        if(left < right){
//            int middle = (left+right)/2;
//            sort(arr,left,middle,temp);
//            sort(arr,middle+1,right,temp);
//            merge(arr, left, middle, right, temp);
//        }
//
//    }
//
//    private void merge(int[] arr, int left, int middle, int right, int[] temp){
//        int i=left;
//        int j=middle+1;
//        int t = 0;
//        while (i<=middle && j <= right){
//            if(arr[i]<=arr[j]){
//                temp[t++] = arr[i++];
//            }else {
//                temp[t++] = arr[j++];
//            }
//        }
//        while (i<=middle){
//            temp[t++] = arr[i++];
//        }
//        while (j<=right){
//            temp[t++] = arr[j++];
//        }
//        t = 0;
//        while (left<=right){
//            arr[left++] = temp[t++];
//        }
//
//    }
    private void sort1(int[] arr, int left, int right, int[] temp){
        if(left < right){
            int mid = (left + right)/2;
            sort1(arr, left, mid, temp);
            sort1(arr, mid+1, right, temp);
            merge1(arr, left, mid, right, temp);
        }
    }

    private void merge1(int[] arr, int left, int mid, int right, int[] temp){
        int i=left;
        int j=mid+1;
        int t =0;
        while (i<=mid && j<= right ){
            if(arr[i] <= arr[j]) {
                temp[t++] = arr[i++];
            } else {
                temp[t++] = arr[j++];
            }
        }
        while (i<=mid){
            temp[t++] = arr[i++];
        }
        while (j<=right){
            temp[t++] = arr[j++];
        }
        t = 0;
        while (left<=right){
            arr[left++] = temp[t++];
        }
    }

}
